/*
 * @lc app=leetcode.cn id=973 lang=javascript
 *
 * [973] 最接近原点的 K 个点
 */

// @lc code=start
/**
 * @param {number[][]} points
 * @param {number} K
 * @return {number[][]}
 */
var kClosest = function (points, K) {
  /**
   * @type {number[dist][index]}
   */
  const queue = [];
  // 初始化K个值的队列
  for (let i = 0; i < K; i++) {
    const point = points[i];
    const [x, y] = points[i];
    const dist = Math.pow(x, 2) + Math.pow(y, 2);
    queue.push([dist, i]);
  }
  queue.sort((a, b) => b[0] - a[0]);
  // 从K+1开始比较，成功入队并出队1个
  for (let i = K; i < points.length; i++) {
    const [x, y] = points[i];
    const dist = Math.pow(x, 2) + Math.pow(y, 2);
    if (dist < queue[0][0]) {
      queue.push([dist, i]);
      queue.shift();
      queue.sort((a, b) => b[0] - a[0]);
    }
  }

  const result = [];
  queue.forEach((item) => result.push(points[item[1]]));

  return result;
};
// @lc code=end

/**
 * 时间复杂度：O(nlogK)，其中 n 是数组 points 的长度
 * 空间复杂度：O(K)，因为优先队列中最多有 K 个点
 */
